import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 手动实现一个冒泡排序：并测算处理80000个排序，需要花费多少时间? 本人电脑：10秒
 */
public class BubbleSortDemo {

    public static void main(String[] args) {
        int[] arr = new int[]{3,9,-1,10,20};
        System.out.println("排序前数组：");
        System.out.println(Arrays.toString(arr));
        //调用冒泡排序方法
        bubbleSort(arr);
        System.out.println("排序后数组：");
        System.out.println(Arrays.toString(arr));
        System.out.println("-----------------------------------------");


        //测试冒泡排序的时间复杂度：
        //若处理80000个排序，需要花费多少时间? 本人电脑花费10秒
        bubbleSortTest();
    }

    //测试冒泡排序的时间复杂度：
    //测试算法：若处理80000个排序，需要花费多少时间? 本人电脑花费10秒
    public static void bubbleSortTest(){
        int[] arr = new int[80000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
//        System.out.println(Arrays.toString(arr));

        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间："+s1);
        //进行排序
        bubbleSort(arr);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间："+s2);
    }

    //冒泡排序算法
    public static void bubbleSort(int[] arr){
        //中间值变量
        int temp = 0;
        //打标记
        boolean flag = true;
        //1.先确定总共需要进行多少次冒泡排序
        for (int i = 0; i < arr.length-1; i++) {
            //2.再进行每一次冒泡排序循环
            //注意循环次数要减 i（每次循环次数要减一，且从头开始）,因为第一次循环4次，第二次循环3次，第三次循环2次。。。。
            for (int j = 0; j < arr.length-1-i; j++) {
                //3.若存在前一个数比后一个数大的情况，则交换两个数的位置
                if (arr[j] > arr[j+1]) {
                    flag = false;   //若交换顺序，则改变标记
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

            //优化代码：若在某次冒泡排序循环中，一次交换都没有，则说明该数组此时已经是最终顺序了,可以直接结束程序
            if (flag) {
                break;
            }else {
                //每次比较完，要及时重置标记值，不然只要存在交换一次，后面的数字依然要进行循环比较，这样优化代码就没有意义了
                flag = true;
            }
        }
    }
}
